/*
 * @Author: zxc
 * @Date: 2020-08-15 16:15:02
 * @LastEditTime: 2020-08-15 20:17:11
 * @LastEditors: zxc
 * @Description: 计数排序
 */
import { findMaxValue } from "../utils";
export function countingSort(array) {
  if (array.length < 2) {
    return array;
  }
  const maxValue = findMaxValue(array);
  let sortedIndex = 0;
  const counts = new Array(maxValue + 1);
  array.forEach((e) => {
    if (!counts[e]) {
      counts[e] = 0;
    }
    counts[e]++;
  });
  counts.forEach((e, i) => {
    while (e > 0) {
      array[sortedIndex++] = i;
      e--;
    }
  });
  return array;
}
